import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: DELL
 * Date: 2023-07-29
 * Time: 11:31
 */
public class SelectSort {

    /**
     * 时间复杂度 : O(N ^ 2) - 有序无序遍历都是这么多
     * 空间复杂度 : O(1)
     * 是一个不稳的排序, 并且效率非常差
     */
    public void selectSort(int[] array) {
        for(int i = 0; i < array.length - 1; i++) {
            // 保存当前位置下标作为最小值下标
            int minIndex = i;
            // 从 i 下一个位置开始向后遍历, 寻找最小值的下标
            for(int j = i + 1; j < array.length; j++) {
                // 遇到比 minIndex 值小的就交换下标
                if(array[j] < array[minIndex]) {
                    minIndex = j;
                }
            }

            // 找到最小值下标只有,
            // 下标相同位置不需要交换. 说明当前 i 位置下标就是对应数组最小值, 无需和自己比较
            if(minIndex != i) {
                int tmp = array[minIndex];
                array[minIndex] = array[i];
                array[i] = tmp;
            }

        }
    }

    /**
     * 采用二分的形式进行分组选择最大最小直接交换
     */
    public void selectSort2(int[] array) {
        int left = 0;
        int right = array.length - 1;

        while(left < right) {
            int minIndex = left;
            int maxIndex = left;
            // 定义一个 i 从区间左边下一个数开始寻找到区间右边界
            for(int i = left + 1; i <= right; i++) {
                // 区间内找到了最小值
                 if(array[i] < array[minIndex]) {
                     // 记录更新最小值下标
                     minIndex = i;
                 }

                 if(array[i] > array[maxIndex]) {
                     maxIndex = i;
                 }
            }

            // 此时 minIndex 和 maxIndex 中存放的就是当前[left, right] 这组分组中的最大值和最小值的下标
            // 将最小值换到边界左边 left
            swap(array, minIndex, left);

            // TODO : 此时, 如果 max 下标正好是 left, 说明这个数组中 0 下标是最大的.
            //        max 正好为 left, 进过交换后, 已经把 left 元素换到了 minIndex 元素
            //        再来交换最大值到最后面时, 最大值下标已经变成了 minIndex, 不再是原本的 maxIndex 了
            if(maxIndex == left) {
                maxIndex = minIndex;
            }

            // 最大值交换到有边界 right
            swap(array, maxIndex, right);

            // 缩小边界, 之前的已经有序了
            left++;
            right--;
        }
    }

    /**
     * 交换两个数组对应下标的值
     * @param array 排序数组
     * @param index 交换的下标
     * @param boundary 边界下标
     */
    public void swap(int[] array, int index, int boundary) {
        int tmp = array[index];
        array[index] = array[boundary];
        array[boundary] = tmp;
    }

    public static void main(String[] args) {
        SelectSort selectSort = new SelectSort();
        int[] array = {9, 2, 5, 1, 7};
        selectSort.selectSort2(array);
        System.out.println(Arrays.toString(array));
    }
}
